package me.qingy.old.binary_search;

import java.util.Arrays;
import java.util.HashMap;

/**
 * @author qingy
 * @since 2021/1/29
 */
public class FindDuplicate {
    /**
     * 方法一：HashMap HashSet
     * 时间复杂度 O(n)
     * 空间复杂度 O(n)
     */
    public int findDuplicate1(int[] nums) {
        HashMap<Integer, Integer> countMap = new HashMap<>();
        for (int num : nums) {
            if (countMap.containsKey(num))
                return num;
            else
                countMap.put(num, 1);
        }
        return -1;
    }

    /**
     * 方法二：排序比较相邻
     * 时间复杂度 O(nlogn)
     * 空间复杂度 O(1)
     */
    public int findDuplicate2(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i]==nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }

    /**
     * 方法三：抽屉原理：三本书放两个抽屉，那么每个抽屉中书的数量必然小于等于二
     * 时间复杂度 O(nlogn)
     * 空间复杂度 O(1)
     */
    public int findDuplicate3(int[] nums) {
        Arrays.sort(nums);
        for (int i = 0; i < nums.length-1; i++) {
            if (nums[i]==nums[i+1]){
                return nums[i];
            }
        }
        return -1;
    }
}
